package com.kevinkk.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
 * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
 *
 * 集合中含有重复元素，因此需要用 used 数组来去重
 */

public class SubsetsII {
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        public List<List<Integer>> subsetsWithDup(int[] nums) {
            int[] used = new int[nums.length];
            Arrays.sort(nums);
            backtracking(nums, used, 0);
            return res;
        }

        private void backtracking(int[] nums, int[] used, int startIndex){
            res.add(new ArrayList<>(path));

            for(int i = startIndex; i < nums.length; i++){
                if(i > 0 && nums[i] == nums[i-1] && used[i-1] == 0) continue;
                path.add(nums[i]);
                used[i] = 1;
                backtracking(nums, used, i+1);
                used[i] = 0;
                path.remove(path.size()-1);
            }
        }
    }
}
